/*
 * 1145.删除链表中的元素
 * 删除链表中等于给定值val的所有节点。
 * https://www.lintcode.com/problem/remove-linked-list-elements/description
 * 
 * 样例
 * 给出链表 1->2->3->3->4->5->3, 和 val = 3, 你需要返回删除3之后的链表：1->2->4->5。
 */
package Remove_Linked_List_Elements_1452;

class ListNode {
	int val;
	ListNode next;
	ListNode(int x) {
		val = x;
		next = null;
	}
}

public class Remove_Linked_List_Elements_1452 {

	/**
	 *Definition for ListNode
	 **/



	/**
	 * @param head: a ListNode
	 * @param val: An integer
	 * @return: a ListNode
	 */
	public static ListNode removeElements(ListNode head, int val) {
		// write your code here
		if(head != null) {
			//			ListNode newNode = null;
			//			newNode = new ListNode(head.val);
			//			ListNode p = head.next;
			//			ListNode newP = newNode;
			//			while(p != null) {
			//				if(p.val != val) {
			//					ListNode tmp = new ListNode(p.val);
			//					newP.next = tmp;
			//					newP = tmp;
			//				} 
			//				p = p.next;
			//			}
			boolean i = false;
			ListNode newNode = null;
			ListNode newP = null;
			ListNode p = head;
			while(p != null) {
				if(p.val != val) {
					if(i) {
						ListNode tmp = new ListNode(p.val);
						newP.next = tmp;
						newP = tmp;
					} else {
						newNode = new ListNode(p.val);
						newP = newNode;
						i = true;
					}
				}
				p = p.next;
			}
			return newNode;
		} else {
			return head;
		}
	}


	public static void main(String[] args) {
		// TODO Auto-generated method stub
		// 1->2->3->3->4->5->3
		ListNode head = new ListNode(1);
		ListNode p1 = new ListNode(2);
		ListNode p2 = new ListNode(3);
		ListNode p3 = new ListNode(3);
		ListNode p4 = new ListNode(4);
		ListNode p5 = new ListNode(5);
		ListNode p6 = new ListNode(3);
		head.next = p1;
		p1.next = p2;
		p2.next = p3;
		p3.next = p4;
		p4.next = p5;
		p5.next = p6;
		ListNode p = removeElements(head,3);
		while(p != null) {
			System.out.println(p.val);
			p = p.next;
		}
	}

}
